﻿\subsection{Поиск запрещённых подслов}
\label{subsection:bigexp-forbidden}

В этом параграфе мы рассмотрим, как с помощью суффиксного массива
и массива $lcp$ корня $r$ проверять, будет ли запрещённое подслово $u$,
построенное по корню $r$, минимальным запрещённым. Эта проверка
используется в основном алгоритме построения антисловаря языка
первого уровня (стр.~\pageref{pr-bigexp}).

\begin{lmm} \label{forblen}
Пусть $r\in L$, где $L$~--- язык первого уровня над алфавитом размера $k$. Тогда суффикс
$s$ слова $r$ встречается в $r$ не более $\lceil\frac{|r|}{|s|(k-2)}\rceil$ раз.
\end{lmm}
\begin{proof}
Пусть $s$ является $j$-м суффиксом $r$ и входит в строку $r$ начиная с $i$-го ($i < j$)
символа. Заметим, что вхождения $s$ не пересекаются, поскольку в противном случае
в $r$ будет содержаться квадрат, а квадраты запрещены в языках первого уровня.
Подслово длины $j-i+|s|$, начинающееся с $i$-го символа, является $\frac{j-i+|s|}{j-i}$-степенью,
а значит, $\frac{j-i+|s|}{j-i} \le \frac{k-1}{k-2}$, откуда $j-i \ge |s|(k-2)$.
Поскольку разность между двумя соседними вхождениями $s$ ограничена снизу
$|s|(k-2)$, количество вхождений не может быть больше $\lceil\frac{|r|}{|s|(k-2)}\rceil$.
\end{proof}

\begin{crllr} \label{forblen-cor}
Пусть $r\in L$, где $L$~--- язык первого уровня над алфавитом размера $k$.
\begin{itemize}
\item[(1)] Если $s$~--- суффикс $r$, $|s| > \frac{|r|}{k-2}$, то в $r$ нет суффикса $st$ при $|t| > 0$.
\item[(2)] Количество пар $(s, st)$, где $s$ и $st$~--- суффиксы $r$ ($|t| > 0$),
не превосходит $O(\frac{|r|^2}{k^2})$.
\end{itemize}
\end{crllr}

\begin{proof}
(2) По лемме~\ref{forblen}, количество пар $(s, st)$ для каждого суффикса $s$ составляет
$O(\frac{|r|}{k})$. Поскольку, согласно (1), длина $s$ может иметь $O(\frac{|r|}{k})$ различных
значений, общее количество пар $(s,st)$ составляет $O(\frac{|r|^2}{k^2})$.
\end{proof}

Рассмотрим, как можно организовать перебор пар суффиксов $(s, st)$ слова $r$. Все суффиксы
вида $st$ идут в $suff_r$ после $s$. Это значит, что достаточно найти позицию $s$ в $suff_r$,
после чего последовательно просматривать суффиксы справа от этой позиции до тех пор, пока
длина их $lcp$ с $s$ не станет меньше $|s|$. Мы будем использовать эти пары суффиксов, например,
при проверке того, появится ли в корне $r$ запрещённый суффикс при дописывании к нему буквы~$c$.

\begin{lmm} \label{forb-append}
Пусть $r\in L$, где $L$~--- язык первого уровня над алфавитом $\Sigma$, $c\in\Sigma$.
Тогда $rc \in L$ в том и только в том случае если:
\begin{enumerate}
\item Суффикс длины $k-1$ слова $rc$ состоит из различных букв.
\item Не существует такой пары суффиксов $(s,st)$ слова $r$, что $t$ начинается с буквы $c$,
и слово $stc$ является запрещённой в языке $L$ $\frac{|st|+1}{|s|+1}$-степенью.
\end{enumerate}
\end{lmm}

\begin{proof}
Если $rc$ лежит в языке первого уровня, то любое подслово $rc$ длины $k{-}1$ должно состоять
из различных букв, и в $rc$ не может быть запрещённых подслов. Докажем утверждение в обратную
сторону. Пусть, от противного, $rc \notin L$. Поскольку $r \in L$, то в $rc$ есть запрещённый
суффикс $xyx$. Если $|x|=1$, то $xyx$ является $\frac{p+1}{p}$-степенью, и
$\frac{p+1}{p} > \frac{k}{k-1}$, откуда $p < k{-}1$, то есть, какие-то две буквы из суффикса
длины $k{-}1$ слова $rc$ совпадают. Если же $|x|>1$, то запрещённый суффикс $xyx$ можно записать как
$\bar{x}cy\bar{x}c$. Обозначив $\bar{x}$ как $s$, а $cy\bar{x}$ как $t$ мы получим пару
суффиксов $(s,st)$ слова $r$, удовлетворяющую ограничениям в условии леммы.
\end{proof}

Обратимся к построению антисловаря $\beta$-свободного языка. Пусть $r=xy$~--- корень
некоторого слова, а $u=xyx$~--- запрещённое подслово, построенное по этому корню. Если $u$
не входит в антисловарь, то в $u$ содержится подслово $ztz$, такое что $\frac{|ztz|}{|zt|} \ge \beta$.
Поскольку $r$ не содержит запрещённых подслов по построению, возможны следующие три случая
(в случаях $(a)$ и $(b)$ $z = z1z2$).

\begin{center}
\includegraphics{pictures/bigexp-xyx-a.pdf}
\includegraphics{pictures/bigexp-xyx-b.pdf}
\includegraphics{pictures/bigexp-xyx-c.pdf}
\end{center}

Опишем проверку того, выполняется ли какой-либо из случаев $(a)$ и $(b)$.
Рассмотрим все пары суффиксов $(s, st)$ корня $r$.
Пара $(s, st)$ означает, что суффикс $s$ входит в корень $r$ начиная
с $i$-й позиции ($i < |r|{-}|s|{+}1$). Обозначим $s$
как $z1$, вычислим длину $z2$ как длину $lcp$ всего корня $r$ и $(i{+}|z1|)$-го суффикса
$r$ (случай $(b)$ возможен, если $z1$ целиком входит в $x$, причём в этом случае длина
$z2$ должна быть такой, чтобы $z2tz1z2$ также целиком входило в $x$). Теперь, поскольку
мы знаем длину $z$ и расстояние между двумя вхождениями $z$ в слово $u$, мы можем проверить,
является ли слово $ztz$ запрещённым, посчитав его экспоненту. На этом проверка заканчивается.

Посчитаем для каждой пары суффиксов $(s, st)$ корня $r$, сколько произвольных
букв можно дописать к корню так, что при этом два вхождения $s$ образуют в построенном по
корню запрещённом слове подслово $sqs$ с запрещённой экспонентой. Для этого нам понадобится
следующая лемма.

\begin{lmm} \label{forbseg}
Пусть $r, \bar{r} \in L$, где $L$~--- $\beta$-свободный язык первого уровня. $r$~--- префикс
$\bar{r}$, суффикс $s$ входит в $r$ начиная с $i$-й и с $(|r|{-}|s|{+}1)$-й позиции. Запрещённое
слово $\bar{u}$, построенное по корню $\bar{r}$ содержит запрещённое подслово $sqs$, начинающееся
с $(|r|{-}|s|{+}1)$-й позиции, если:
\begin{itemize}
\item[(1)] $\lceil|\bar{r}|(\beta-1)\rceil \ge i+|s|-1$
\item[(2)] $\frac{|s|}{|\bar{r}|-|r|+|s|+i-1} \ge \beta-1$
\end{itemize}
\end{lmm}
\begin{proof}
Пусть $\bar{r} = xy$, $\bar{u} = xyx$. Первое неравенство следует из того, что
левое вхождение $s$ в $\bar{r}$ должно целиком попасть в $x$, а второе~---
из условия запрещённости слова $sqs$, т.е. из неравенства $\frac{sqs}{sq} \ge \beta$.
\end{proof}

С помощью неравенств, приведённых в лемме~\ref{forbseg}, мы можем по корню $r$ и паре
встречающихся в нём суффиксов $(s, st)$ найти интервал значений длины корня $\bar{r}$,
начинающегося с $r$, при которых $\bar{r}$ заведомо не является корнем минимального
запрещённого слова. Заметим, что этот интервал может быть пустым. Обозначим объединение
этих интервалов для фиксированных $r$ и $s$ как $badLengths(r,s)$. В процессе рекурсивного
перебора корней запрещённых слов, во время обработки корня $\bar{r}$, мы будем
рассматривать объединение $badLengths(r,s)$ для всех $r$, являющихся префиксами
$\bar{r}$, и подходящих суффиксов $s$. В том случае, если $|\bar{r}|$ содержится в этом
объединении, то выполняется случай $(c)$ (см. рис. выше), и $\bar{r}$ заведомо
не является корнем минимального запрещённого слова. В противном случае, мы сможем
проверить, выполняются ли случаи $(a)$ и $(b)$ описанным выше способом. Если и они
не выполняются, то необходимо достроить $\bar{r}$ до минимального запрещённого слова
и добавить его код Пансьё в антисловарь.

Мы завершаем этот параграф описанием реализации рекурсивного алгоритма перебора корней
запрещённых слов, приведённого на стр.~\pageref{pr-bigexp}. Ниже $r$ обозначает рассматриваемый
корень, $B$~--- множество длин, которые не может иметь корень минимального запрещённого
слова, начинающийся с $r$.
\texttt{\begin{tabbing}
\noindent\textsc{build}($r, B$) (рекурсивный перебор корней). \label{pr-bigexp-concrete} \\
01. для \= всех суффиксов $s$ корня $r$\\
02. \> перебрать пары суффиксов $(s, st)$ и построить $badLenghts(r,s)$\\
03. \> $B \leftarrow B \cup badLengths(r,s)$\\
04. если \= $|r| \notin B$\\
05. \> если \= не выполняются случаи $(a)$ и $(b)$\\
06. \>\> построить по корню $r$ запрещённое слово $u$\\
07. \>\> добавить $P(u)$ в антисловарь\\
08. если \= $|r| < R$\\
09. \> для \= $c \in \{0,1\}$\\
10. \>\> $rn \leftarrow P^{-1}(P(r) + c)$\\
11. \>\> если \= в $rn$ нет запрещённого суффикса\\
12. \>\>\> построить $suff_{rn}$ и $lcp_{rn}$\\
13. \>\>\> \textsc{build}($rn, B$)\\
14. конец процедуры\\
\end{tabbing}}
По лемме~\ref{forblen-cor} цикл в строках 1-3 и проверки в строках 5 и 11
можно осуществить за $O(\frac{|r|^2}{k^2})$. В
параграфе~\ref{subsection:bigexp-sufarr} описан алгоритм построения суффиксного массива
и массива $lcp$ в строке 12 за $O(|r|)$. Общее время обработки одного корня
(без учёта добавления слова $u$ в антисловарь) составляет
$O(|r| + \frac{|r|^2}{k^2})$. Как уже отмечалось выше,
количество перебираемых корней для языков первого уровня значительно превосходит
количество слов из антисловаря.
